package nineteenthDay;

import java.util.HashMap;
import java.util.Map;

public class ContainsNearbyAlmostDuplicate {
//    public static void main(String[] args) {
//        int[] nums = {1,5,9,1,5,9};
//        System.out.println(containsNearbyAlmostDuplicate(nums,2,3));
//    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//        if (nums.length < 2){
//            return false;
//        }
//        for (int i = 0; i < nums.length - 1; i++) {
//            for (int j = i + 1; j < Math.min(i + k + 1, nums.length); j++) {
//                Long sub = (long) nums[i] - (long) nums[j];
//                System.out.println(sub);
//                if (Math.abs(sub) <= (long) t){
//                    return true;
//                }
//            }
//        }
//        return false;
        //n方复杂度，过高
        int n = nums.length;
        Map<Long, Long> map = new HashMap<Long, Long>();
        long w = (long) t + 1;
        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }
            map.put(id, (long) nums[i]);
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }
    public long getID(long x, long w) {
        if (x >= 0) {
            return x / w;
        }
        return (x + 1) / w - 1;
    }
}
